package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2022-01-11 10:34
 * @description: Functions of this class is
 * 动态规划官方题解：
 * class Solution {
 *     public int[] countBits(int n) {
 *         int[] bits = new int[n + 1];
 *         int highBit = 0;
 *         for (int i = 1; i <= n; i++) {
 *             if ((i & (i - 1)) == 0) {//如果判断到当前的整数为：2的整数次幂，
 *                 highBit = i;
 *             }
 *             bits[i] = bits[i - highBit] + 1;//则可以使用动态规划，将每次要进行计算的数，都去和之前算到的最高位去规划，然后+1<最高位数字的1个数>
 *                 //就能得到答案
 *         }
 *         return bits;
 *     }
 * }
 *
 **/
public class No比特位计数 {
    public int[] countBits(int n) {
        int ans[] = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            ans[i] = judge(i);
        }
        return ans;
    }

    public int judge(int x) {
        if (x < 2) {
            return x;
        }
        int tot = 0;
        while (x != 0) {
            if ((x & 1) == 1) {
                ++tot;
            }
            x >>= 1;
        }
        return tot;
    }

}